import java.awt.Color;
import java.awt.Graphics;

import javax.swing.JPanel;

@SuppressWarnings("serial")
public class ArvoreBinaria extends JPanel {
	
	Node root;
	Graphics g;
	public int painel_width;
	final int DELTA = 200;

	public ArvoreBinaria(int n) {
		
		// Cor do BackGround
		setBackground(Color.WHITE);
		// seta o Layout da Classe
		setLayout(null);
		//Árvore
		root = null;
		painel_width = n; // recebe o tamanho do painel arvores.
	}

	// ::::::::::Função que desenha::::::::::::

	// ::::::::::Verifica se vazia:::::::::::::
	public boolean vazia() {
		return root == null;
	}
	
	public void InserirAPartirDaRaiz (int n) {
		Inserir(n, 0, 0, DELTA, null, root);
	}

	// :::::::::::::::::::Função Inserir::::::::::::::::::::
	public void Inserir(int n, int posx, int posy, int delta, Node novo,
			Node aux) {

		if (aux != null) // Não permite que se coloque número ja contidos na
							// arvore
			if (aux.getNumero() == n)
				return;

		if (delta < 15) // limita o delta a fica maior que 18
			delta = 15;
		if (novo == null) {
			novo = new Node(n);
		}
		if (vazia()) {
			root = novo;
			root.setPosition((painel_width / 2) - root.getWidth() / 2, 30);
			root.pai = null;
			this.add(root);
			return;
		}
		boolean cond1 = (aux.getNumero() < n && aux.direito == null), cond2 = (aux
				.getNumero() < n && aux.direito != null), cond3 = (aux
				.getNumero() > n && aux.esquerdo == null);

		if (cond1) {
			aux.direito = novo;
			(aux.direito).pai = aux;
			(aux.direito).setPosition(aux.x + delta, aux.y + 60);
			this.add(aux.direito);
			// Inserir Linha.
//			aux.direito = new Linha(aux.x, aux.y, aux.direito.x,
//					aux.direito.y, false);
			add(aux.l_direita);
		} else if (cond2) {
			Inserir(n, aux.x, aux.y, (6 * delta) / 11, novo, aux.direito);
		} else if (cond3) {
			aux.esquerdo = novo;
			aux.esquerdo.pai = aux;
			aux.esquerdo.setPosition(aux.x - delta, aux.y + 60);
			this.add(aux.esquerdo);
			// Insere linha
			aux.l_esquerda = new Linha(aux.x, aux.y, aux.esquerdo.x,
					aux.esquerdo.y, true);
			add(aux.l_esquerda);

		} else {
			Inserir(n, aux.x, aux.y, (6 * delta) / 11, novo, aux.esquerdo);
		}

	} // Inserir
		// ::::::::::::::::::::Função de reposicionamento da arvore a partir do
		// nó indicado:::::::::::::::

	public void Reposicione(int x, int y, int delta, Node aux) {
		remove(aux);
		aux.setPosition(x, y);
		add(aux);
		// Recursão
		if (aux.direito != null)
			Reposicione(aux.x + delta, aux.y + 60, (6 * delta) / 11,
					aux.direito);
		if (aux.esquerdo != null)
			Reposicione(aux.x - delta, aux.y + 60, (6 * delta) / 11,
					aux.esquerdo);

		// Trabalho com linhas
		if (aux.l_direita != null)
			remove(aux.l_direita);
		if (aux.l_esquerda != null)
			remove(aux.l_esquerda);
		if (aux.direito != null) {
			aux.l_direita = new Linha(aux.x, aux.y, aux.direito.x,
					aux.direito.y, false);
			add(aux.l_direita);
		}
		if (aux.esquerdo != null) {
			aux.l_esquerda = new Linha(aux.x, aux.y, aux.esquerdo.x,
					aux.esquerdo.y, true);
			add(aux.l_esquerda);
		}
	}

	// ::::::::::::::::::::::: Função que Busca
	// :::::::::::::::::::::::::::::::::::

	public Node Busca(int n, Node aux) {

		if (n == aux.getNumero())
			return aux;
		else if (n > aux.getNumero() && aux.direito != null)
			return Busca(n, aux.direito);
		else if (n < aux.getNumero() && aux.esquerdo != null)
			return Busca(n, aux.esquerdo);
		return null;
	}

	// ::::::::::::::::::::::: Função de Remoção
	// ::::::::::::::::::::::::::::::::::

	public void Remover(int n) {
		Node aux = Busca(n, root);

		if (aux == null)
			return;

		// Caso Especial - Raiz -
		if (aux == root) {
			if (aux.esquerdo == null && aux.direito == null) {
				root = null;
			} else if (aux.direito != null) {
				root = aux.direito;
				aux.direito.pai = null;

				// Procura um lugar vazio a esquerda de aux.esquerdo.
				Node aux2 = aux.direito;
				if (aux.esquerdo != null) {
					while (aux2.esquerdo != null)
						aux2 = aux2.esquerdo;

					aux2.esquerdo = aux.esquerdo;
					aux2.esquerdo.pai = aux2;

				}
				Reposicione(aux.x, aux.y, 300, aux.direito);
			} else if (aux.esquerdo != null) {
				root = aux.esquerdo;
				aux.esquerdo.pai = null;

				// Procura um lugar vazio a direita de aux.direito
				if (aux.direito != null) {
					Node aux2 = aux.esquerdo;
					while (aux2.direito != null)
						aux2 = aux2.direito;

					aux2.direito = aux.direito;
					aux2.direito.pai = aux2;
				}
				Reposicione(aux.x, aux.y, 300, aux.esquerdo);
			}
			remove(aux);
			if (aux.l_direita != null)
				remove(aux.l_direita);
			if (aux.l_esquerda != null)
				remove(aux.l_esquerda);
			return;
		}

		int delta = aux.pai.x - aux.x; // distancia horizontal entre o pai do
										// elemento a ser removido e ele.
		if (delta < 0) // distancia nao pode ser negativo.
			delta = -delta;

		if (aux.pai.direito == aux) {

			if (aux.esquerdo == null && aux.direito == null) {
				aux.pai.direito = null;
			} else if (aux.direito != null) {
				aux.pai.direito = aux.direito;
				aux.direito.pai = aux.pai;

				// Procura um lugar vazio a esquerda de aux.esquerdo.
				Node aux2 = aux.direito;
				if (aux.esquerdo != null) {
					while (aux2.esquerdo != null)
						aux2 = aux2.esquerdo;
					aux2.esquerdo = aux.esquerdo;
					aux2.esquerdo.pai = aux2;
				}
			} else if (aux.esquerdo != null) {
				aux.pai.direito = aux.esquerdo;
				aux.esquerdo.pai = aux.pai;

				// Procura um lugar vazio a direita de aux.direito
				if (aux.direito != null) {
					Node aux2 = aux.esquerdo;
					while (aux2.direito != null)
						aux2 = aux2.direito;
					aux2.direito = aux.direito;
					aux2.direito.pai = aux2;
				}
			}
		} else {
			if (aux.esquerdo == null && aux.direito == null) {
				aux.pai.esquerdo = null;
			} else if (aux.direito != null) {
				aux.pai.esquerdo = aux.direito;
				aux.direito.pai = aux.pai;

				// Procura um lugar vazio a esquerda de aux.esquerdo.
				Node aux2 = aux.direito;
				if (aux.esquerdo != null) {
					while (aux2.esquerdo != null)
						aux2 = aux2.esquerdo;
					aux2.esquerdo = aux.esquerdo;
					aux2.esquerdo.pai = aux2;
				}

			} else if (aux.esquerdo != null) {
				aux.pai.esquerdo = aux.esquerdo;
				aux.esquerdo.pai = aux.pai;

				// Procura um lugar vazio a direita de aux.direito
				if (aux.direito != null) {
					Node aux2 = aux.esquerdo;
					while (aux2.direito != null)
						aux2 = aux2.direito;
					aux2.direito = aux.direito;
					aux2.direito.pai = aux2;
				}
			}
		}
		// Faz o reposicionamento dos elementos
		Reposicione(aux.pai.x, aux.pai.y, delta, aux.pai);
		// remove da interface
		remove(aux);
		// removendo linhas
		if (aux.l_direita != null)
			remove(aux.l_direita);
		if (aux.l_esquerda != null)
			remove(aux.l_esquerda);
	} // Remover
}
